package com.coder.algorithm.struct;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 *
 * @author yuhushuan
 * @date 2020/6/1 00:08
 */
public class BinaryTreeNode {
    public int value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    public BinaryTreeNode parent;

    public BinaryTreeNode() {
    }

    public BinaryTreeNode(int value) {
        this.value = value;
    }

    // 二叉树功能相关


    /**
     * 判断一棵树是否是完全二叉树
     * <p>
     * 1、如果树为空，则直接返回错
     * 2、如果不为空，层序遍历二叉树
     * 2.1、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
     * 2.2、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
     * 2.3、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；
     * 该树才是完全二叉树，否则就不是完全二叉树；
     *
     * @param root
     * @return
     */
    public static boolean isCompleteBinaryTree(BinaryTreeNode root) {
        // 1. 树为空，返回错误
        if (root == null) {
            return false;
        }
        // 2. 树不为空
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        BinaryTreeNode node;
        while (!queue.isEmpty()) {
            node = queue.peek();
            // 2.1 如果该节点两个孩子都有，则直接poll
            if (node.left != null && node.right != null) {
                queue.poll();
                queue.offer(node.left);
                queue.offer(node.right);
            }
            // 2.2 如果该节点左孩子为空，右孩子不为空，则一定不是完全二叉树
            if (node.left == null && node.right != null) {
                return false;
            }
            // 2.3 如果该节点右孩子为空则为最后一个父节点或者第一个叶子节点，则该节点之后的所有结点都是叶子节点
            if (node.right == null) {
                if (node.left != null) {
                    queue.offer(node.left);
                }
                queue.poll();// 则该节点之后的所有结点都是叶子节点
                while (!queue.isEmpty()) {
                    node = queue.poll();
                    if (node.left == null && node.right == null) {
                        queue.poll();
                    } else {
                        return false;
                    }
                }
                return true;
            }
        }
        return true;
    }

    /**
     * 创建一个完全二叉树
     *
     * @param n 节点数
     * @return
     */
    public static BinaryTreeNode createCompleteBinaryTree(int n) {
        if (n <= 0) {
            return null;
        }
        BinaryTreeNode[] nodes = new BinaryTreeNode[n];
        BinaryTreeNode parent;
        for (int i = 0; i < n; ++i) {
            nodes[i] = new BinaryTreeNode(i + 1);

            if (i > 0) {// 非根节点，存在父节点
                // 当编号 (i+1)>1 时，该节点的父节点变为为 (i+1)/2
                parent = nodes[(i - 1) >> 1];
                // 如果值为 i+1 的节点为偶数(即：i为奇数)，则为左子节点
                if ((i & 0x1) == 1) {
                    parent.left = nodes[i];
                } else {
                    parent.right = nodes[i];
                }
            }
        }
        return nodes[0];
    }

    /**
     * 创建所有节点值都相同的完全二叉树
     *
     * @param n     节点数
     * @param value 节点值
     * @return
     */
    public static BinaryTreeNode createCompleteBinaryTree(int n, int value) {
        if (n <= 0) {
            return null;
        }
        BinaryTreeNode[] nodes = new BinaryTreeNode[n];
        BinaryTreeNode parent;
        for (int i = 0; i < n; ++i) {
            nodes[i] = new BinaryTreeNode(value);

            if (i > 0) {// 非根节点，存在父节点
                // 当编号 (i+1)>1 时，该节点的父节点变为为 (i+1)/2
                parent = nodes[(i - 1) >> 1];
                // 如果值为 i+1 的节点为偶数(即：i为奇数)，则为左子节点
                if ((i & 0x1) == 1) {
                    parent.left = nodes[i];
                } else {
                    parent.right = nodes[i];
                }
            }
        }
        return nodes[0];
    }

    /**
     * 创建满二叉树
     *
     * @param h
     * @return
     */
    public static BinaryTreeNode createFullBinaryTree(int h) {
        if (h <= 0) {
            return null;
        }
        int n = (int) Math.pow(2, h) - 1;
        return createCompleteBinaryTree(n);
    }

    public static BinaryTreeNode createOnlyLeftNodeTree(int n) {
        BinaryTreeNode root = null;
        BinaryTreeNode parent = null;

        for (int i = 1; i <= n; ++i) {
            BinaryTreeNode node = new BinaryTreeNode(i);
            if (parent != null) {
                parent.left = node;
            }
            if (root == null) {
                root = node;
            }
            parent = node;
        }
        return root;
    }

    public static BinaryTreeNode createOnlyRightNodeTree(int n) {
        BinaryTreeNode root = null;
        BinaryTreeNode parent = null;

        for (int i = 1; i <= n; ++i) {
            BinaryTreeNode node = new BinaryTreeNode(i);
            if (parent != null) {
                parent.right = node;
            }
            if (root == null) {
                root = node;
            }
            parent = node;
        }
        return root;
    }

    /* **************************************** 遍历 ******************************************** */

    /**
     * 前序遍历-递归
     * <p>
     * 根-> 左-> 右
     *
     * @param node
     */
    public static void preOrderTraversal_Recursively(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        System.out.print(node.value + " ");
        if (node.left != null) {
            preOrderTraversal_Recursively(node.left);
        }
        if (node.right != null) {
            preOrderTraversal_Recursively(node.right);
        }
    }

    /**
     * 前序遍历-非递归（传统）
     * <p>
     * 思路：
     * 1. 节点先作为根访问，放入栈（回溯需要）；将左子节点（非null）作为根节点循环；
     * 2. 如果左子节点为 null ，访问右节点；
     * 3. 将右节点作为根节点，继续 1。
     * <p>
     * 简化后
     * 1. 节点先作为根访问，放入栈（回溯需要）；
     * 2. 如果左子节非 null 继续 1；左子节点为 null，将右节点作为根，继续 1
     *
     * @param node
     */
    public static void preOrderTraversal(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                System.out.print(node.value + " ");
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        System.out.println();
    }

    public static void preOrderTraversal_Simplify(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                System.out.print(node.value + " ");
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                node = node.right;
            }
        }
        System.out.println();
    }

    /**
     * 前序遍历-非递归
     * <p>
     * 根-> 左-> 右
     * <p>
     * 栈先进后出，对于根节点，先访问左节点，必须后进
     *
     * @param node
     */
    public static void preOrderTraversal_Solution2(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();

        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.print(node.value + " ");

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历-递归
     * <p>
     * 左-> 根-> 右
     *
     * @param node
     */
    public static void inOrderTraversal_Recursively(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        if (node.left != null) {
            inOrderTraversal_Recursively(node.left);
        }
        System.out.print(node.value + " ");
        if (node.right != null) {
            inOrderTraversal_Recursively(node.right);
        }
    }

    /**
     * 中序遍历-非递归
     * <p>
     * 左-> 根-> 右
     * <p>
     * 思路：
     * 1. 节点作为根节点放入栈，将左子节点（非null）作为根节点循环入栈。
     * 2. 如果左子节点为 null ，访问节点。
     * 3. 然后将右节点做为根节点，继续 1；
     * 简化后
     * 1. 节点放入栈（回溯需要）；
     * 2. 如果左子节非 null 继续 1；左子节点为 null，将右节点作为根，继续 1
     *
     * @param node
     */
    public static void inOrderTraversal(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            System.out.print(node.value + " ");
            node = node.right;
        }
        System.out.println();
    }

    public static void inOrderTraversal_Simplify(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.print(node.value + " ");
                node = node.right;
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历-递归
     * <p>
     * 左-> 右-> 根
     *
     * @param node
     */
    public static void postOrderTraversal_Recursively(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        if (node.left != null) {
            postOrderTraversal_Recursively(node.left);
        }
        if (node.right != null) {
            postOrderTraversal_Recursively(node.right);
        }
        System.out.print(node.value + " ");
    }

    /**
     * 后序遍历-非递归
     * <p>
     * 左-> 右-> 根
     * <p>
     * 思路：
     * 1.
     *
     * @param node
     */
    public static void postOrderTraversal(BinaryTreeNode node) {
        if (node == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode lastVisit = null;// 标记每次遍历最后一次访问的节点

        while (!stack.isEmpty() || node != null) {
            // 节点不为空，节点入栈，并且指向下一个左孩子
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            // 如果栈不为空
            if (!stack.isEmpty()) {
                // 出栈
                node = stack.pop();
                // 判断 node 是否有右孩子
                // 如果没有，输出该节点；让 lastVisit 指向 node，并让 node 为 null
                if (node.right == null || node.right == lastVisit) {
                    System.out.print(node.value + " ");
                    lastVisit = node;
                    node = null;
                } else {
                    stack.push(node);
                    node = node.right;
                }
            }
        }
        System.out.println();
    }

    /**
     * 层级遍历
     * <p>
     * 把一层的节点放入队列中，打印的同时，把队列中节点的子节点入队列
     *
     * @param root
     */
    public static void levelOrder(BinaryTreeNode root) {
        if (root == null) {
            System.out.println("null");
            return;
        }

        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int currentLevelNum = 0;
        int nextLevelNum = 0;
        currentLevelNum++;

        BinaryTreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.print(node.value + " ");
            currentLevelNum--;

            if (node.left != null) {
                queue.offer(node.left);
                nextLevelNum++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextLevelNum++;
            }
            if (currentLevelNum == 0) {
                System.out.println();
                currentLevelNum = nextLevelNum;
                nextLevelNum = 0;
            }
        }
        System.out.println();
    }

    /**
     * 层级遍历-"之"字形打印
     *
     * @param root
     */
    public static void levelOrderZigzag(BinaryTreeNode root) {
        if (root == null) {
            System.out.println("null");
            return;
        }
        Stack<BinaryTreeNode> stack1 = new Stack<>();
        Stack<BinaryTreeNode> stack2 = new Stack<>();

        stack1.push(root);
        BinaryTreeNode node;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                node = stack1.pop();
                System.out.print(node.value + " ");

                if (node.left != null) {
                    stack2.push(node.left);
                }
                if (node.right != null) {
                    stack2.push(node.right);
                }
            }
            System.out.println();

            while (!stack2.isEmpty()) {
                node = stack2.pop();
                System.out.print(node.value + " ");

                if (node.right != null) {
                    stack1.push(node.right);
                }
                if (node.left != null) {
                    stack1.push(node.left);
                }
            }
            System.out.println();
        }
    }

    /**
     * 绘制二叉树
     * 1. 中序遍历，将节点转成数组，确定节点横向位置
     * 2. 层级遍历，将节点转成数组，确定节点纵向位置，换行符为 null
     * 3. 将中序列表节点的位置存入 HashMap
     *
     * @param root
     */
    public static void drawBinaryTree(BinaryTreeNode root) {
        if (root == null) {
            System.out.println("null");
            return;
        }

        List<BinaryTreeNode> inOrderList = binaryTreeToInOrderList(root);

        // 节点数量
        int n = inOrderList.size();
        Map<BinaryTreeNode, Integer> withMap = new HashMap<>(inOrderList.size());
        for (int i = 0, with = 0; i < n; ++i) {
            // ArrayList#get() 方法时间复杂度为 O(1)
            BinaryTreeNode node = inOrderList.get(i);
            // node 值前后各加一个占位符
            withMap.put(node, with + 1);
            with += 2 + String.valueOf(node.value).length();
        }

        // 打印
        int lineWith = 0;
        StringBuilder line = new StringBuilder();

        int dividerWith = 0;
        StringBuilder divider = new StringBuilder();
        boolean isRootLevel = true;

        List<BinaryTreeNode> levelOrderList = binaryTreeToLevelOrder(root);
        for (BinaryTreeNode node : levelOrderList) {
            if (node != null) {
                String drawDivider = drawNodeDividerToString(node, withMap, dividerWith);
                divider.append(drawDivider);
                dividerWith += drawDivider.length();

                String drawLine = drawNodeToString(node, withMap, lineWith);
                line.append(drawLine);
                lineWith += drawLine.length();
            } else {// 换行
                if (!isRootLevel) {
                    System.out.println(divider);
                }
                divider = new StringBuilder();
                isRootLevel = false;
                dividerWith = 0;

                System.out.println(line.toString());
                line = new StringBuilder();
                lineWith = 0;
            }
        }
    }

    private static String drawNodeToString(BinaryTreeNode node, Map<BinaryTreeNode, Integer> withMap, int startIndex) {
        StringBuilder builder = new StringBuilder();
        int nodeIndex = withMap.get(node);
        if (node.left != null) {
            // 左子节点指向线，减去节点值前 1 个占位符
            int leftIndex = withMap.get(node.left) + 1;
            for (int i = startIndex; i < leftIndex; ++i) {
                builder.append(' ');
            }
            for (int i = leftIndex; i < nodeIndex; ++i) {
                builder.append('_');
            }
        } else {
            for (int i = startIndex; i < nodeIndex; ++i) {
                builder.append(' ');
            }
        }
        builder.append(node.value);
        if (node.right != null) {
            int rightIndex = withMap.get(node.right);
            int len = Integer.toString(node.value).length();
            for (int i = nodeIndex + len; i < rightIndex; ++i) {
                builder.append('_');
            }
        }
        return builder.toString();
    }

    private static String drawNodeDividerToString(BinaryTreeNode node, Map<BinaryTreeNode, Integer> withMap, int startIndex) {
        StringBuilder builder = new StringBuilder();
        int nodeIndex = withMap.get(node);
        for (int i = startIndex; i < nodeIndex; ++i) {
            builder.append(' ');
        }
        builder.append('|');
        return builder.toString();
    }


    private static List<BinaryTreeNode> binaryTreeToInOrderList(BinaryTreeNode root) {
        if (root == null) {
            return null;
        }
        List<BinaryTreeNode> list = new ArrayList<>();
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                list.add(node);
                node = node.right;
            }
        }
        return list;
    }

    private static List<BinaryTreeNode> binaryTreeToLevelOrder(BinaryTreeNode root) {
        if (root == null) {
            return null;
        }
        List<BinaryTreeNode> list = new ArrayList<>();
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int currentLevelNum = 0;
        int nextLevelNum = 0;
        currentLevelNum++;

        BinaryTreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            list.add(node);
            currentLevelNum--;

            if (node.left != null) {
                queue.offer(node.left);
                nextLevelNum++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextLevelNum++;
            }
            if (currentLevelNum == 0) {
                list.add(null);
                currentLevelNum = nextLevelNum;
                nextLevelNum = 0;
            }
        }
        return list;
    }

    /* ===================================== 测试 =========================================== */

    public static void main(String[] args) {
        testCreateOnlyLeftNodeTree();

//        testDrawBinaryTree(getTestBinaryTree_1());
//        testPreOrderTraversal(root);
//        testInOrderTraversal(root);
//        testPostOrderTraversal(root);
//        testLevelOrderTraversal(root);
    }

    private static void testCreateOnlyLeftNodeTree(){
        BinaryTreeNode root = createOnlyLeftNodeTree(5);
        System.out.println("二叉树：");
        drawBinaryTree(root);
    }

    private static void testDrawBinaryTree(BinaryTreeNode root) {
        System.out.println("二叉树：");
        drawBinaryTree(root);
    }

    private static void testPreOrderTraversal(BinaryTreeNode root) {
        System.out.println("二叉树：");
        drawBinaryTree(root);

        System.out.println("前序遍历-递归：");
        preOrderTraversal_Recursively(root);

        System.out.println("\n前序排序-非递归：");
        preOrderTraversal(root);

        System.out.println("前序排序-非递归简化：");
        preOrderTraversal_Simplify(root);

        System.out.println("前序排序-非递归解法2：");
        preOrderTraversal_Solution2(root);
        System.out.println();
    }

    private static void testInOrderTraversal(BinaryTreeNode root) {
        System.out.println("二叉树：");
        drawBinaryTree(root);

        System.out.println("中序遍历-递归：");
        inOrderTraversal_Recursively(root);

        System.out.println("\n中序排序-非递归：");
        inOrderTraversal(root);

        System.out.println("中序排序-非递归简化：");
        inOrderTraversal_Simplify(root);
        System.out.println();
    }

    private static void testPostOrderTraversal(BinaryTreeNode root) {
        System.out.println("二叉树：");
        drawBinaryTree(root);
        System.out.println("后序遍历-递归：");
        postOrderTraversal_Recursively(root);
        System.out.println("\n后序遍历-非递归：");
        postOrderTraversal(root);
        System.out.println();
    }

    private static void testLevelOrderTraversal(BinaryTreeNode root) {
        System.out.println("二叉树：");
        drawBinaryTree(root);
        System.out.println("层级遍历：");
        levelOrder(root);
        System.out.println("层级遍历-之字形：");
        levelOrderZigzag(root);
        System.out.println();
    }

    /*
           1
         /   \
       2       3
      /       / \
     4       5   6
      \         /
       7       8
     */
    public static BinaryTreeNode getTestBinaryTree_1() {
        // [1, 2, 4, 7, 3, 5, 6, 8]
        BinaryTreeNode[] nodes = new BinaryTreeNode[9];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new BinaryTreeNode();
            nodes[i].value = i;
        }

        BinaryTreeNode root = nodes[1];
        nodes[1].left = nodes[2];
        nodes[1].right = nodes[3];

        nodes[2].left = nodes[4];
        nodes[4].right = nodes[7];

        nodes[3].left = nodes[5];
        nodes[3].right = nodes[6];

        nodes[6].left = nodes[8];
        return root;
    }


}
